package com.zhupf.part7;

/**
 * @author zhupf
 * @date 2024年12月04日 16:53
 * @Description
 *
 *  LCR 026. 重排链表
 */
public class ReorderList {

    public static void main(String[] args) {
        ListNode node = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4))));
        reorderList(node);
    }


    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }


    public static void reorderList(ListNode head) {
        if(head == null || head.next ==null){
            return;
        }
        ListNode node = head;
        ListNode midNode = findMidNode(node);
        ListNode midNextNode = midNode.next;
        midNode.next = null;
        ListNode newNode = reverNode(midNextNode);
        ListNode next;
        ListNode next2;
        while (node != null && newNode != null){
            next = node.next;
            next2 = newNode.next;
            node.next = newNode;
            newNode.next = next;
            node = next;
            newNode = next2;
        }
    }

    public static ListNode reverNode(ListNode listNode1){
        ListNode ans = null;
        ListNode next;
        while (listNode1 != null){
            next = listNode1.next;
            listNode1.next = ans;
            ans = listNode1;
            listNode1 = next;
        }
        return ans;
    }

    public static ListNode findMidNode(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}
